Computational Topology
Toolbox
Thomas Reinke
July 1, 2025
Contents
Complexes (Chapter III)
A decomposition of a topological space into simple pieces.
Simplicial Complexes
- Simplex: The convex hull of \(k+1\) affinely independent points. A \(k\)-simplex has dimension \(k\).
- Examples: vertex (0-simplex), edge (1-simplex), triangle (2-simplex), tetrahedron (3-simplex).
- Simplicial Complex: A finite collection of simplices \(K\) such that:
- If \(\sigma \in K\) and \(\tau \le \sigma\) (τ is a face of σ), then \(\tau \in K\).
- If \(\sigma, \, \sigma_0 \in K\), then \(\sigma \cap \sigma_0\) is either empty or a face of both.
Simplicial Complexes
- j-skeleton (\(K^{(j)}\)): The subcomplex consisting of all simplices of dimension \(j\) or less. The 0-skeleton is the vertex set (Vert \(K\)).
- Star: St \(\sigma\) of \(\sigma \in K\) is the set of all simplices \(\tau \in K\) s.t. \(\sigma\) is a face (\(\sigma \le \tau\)).
- Closed Star: \(\overline{\text{St}}\, \sigma\) is the smallest subcomplex containing St \(\sigma\) (i.e., St \(\sigma\) and all their faces).
- Link: Lk \(\sigma\) consists of all simplices in \(\overline{\text{St}}\,\sigma\) that are disjoint from \(\sigma\).
- If \(\tau\) is a vertex, then the link is just the difference between the closed star and the star.
Triangulation
- A triangulation of a topological space \(X\) is a simplicial complex K together with a homeomorphism between \(X\) and the underlying space of \(K\), \(|K|\). A space is triangulable if it has a triangulation.
- Searching a Triangulation: Involves using a data structure that represents a surface’s triangulation to determine its topological properties, such as orientability or genus.
- Ex: Triangulation of a simple closed polygon involves decomposing it into triangles using its vertices and non-intersecting diagonals.
- Ex: Triangulation of a 2-manifold decomposes it into triangular regions homeomorphic to a triangle, where any two triangles meet appropriately (disjoint, shared edge, or shared vertex).
Triangulation
Triangulation
Triangulation
Nerve
- For a finite collection of sets \(\mathcal{F}\), the nerve Nrv \(\mathcal{F}\) is an abstract simplicial complex.
- A subcollection \(X \subseteq \mathcal{F}\) forms a simplex in Nrv \(\mathcal{F}\) if and only if the intersection of all sets in \(X\) is non-empty (\(\bigcap X \ne \emptyset\)).
- Nerve Theorem: Let \(\mathcal{F}\) be a finite collection of closed, convex sets in Euclidean space. Then the nerve of \(\mathcal{F}\) and the union of the sets in \(\mathcal{F}\) have the same homotopy type.
- This also holds if \(\bigcup\mathcal{F}\) is triangulable, all sets in \(\mathcal{F}\) are closed, and all non-empty common intersections are contractible.
Nerve
- Consider a collection of four sets, \(F={A,B,C,D}\). Their intersections are defined as follows:
- Three sets overlap: \(A\), \(B\), and \(C\) all share a common region \(A\cap B \cap C \neq \emptyset\).
- Some pairs overlap: \(D\) intersects with \(B\) and \(C\).
- Some pairs do not: \(D\) does not intersect with \(A\).
Nerve
Nerve
Voronoi Diagram
- A Voronoi Cell (\(V_u\)) is the region of points closer to a site \(u \in S\) than to any other site.
\[ V_u = \{x \in \mathbb{R}^d \mid \|x - u\| \le \|x - v\|, \forall v \in S\} \]
- Each inequality \(\|x - u\| \le \|x - v\|\) defines a half-space. The cell \(V_u\) is the intersection of these half-spaces, which guarantees it is always a convex polygon (in 2D).
- The Voronoi Diagram is the collection of all cells \(\{V_u\}_{u \in S}\), which creates a complete partition (or tessellation) of the space.
Voronoi Diagram
Delaunay Complexes
- The Delaunay Complex is the dual of the Voronoi diagram. More formally, it is the nerve of the collection of Voronoi cells.
- The Rule: A set of sites \(\sigma \subseteq S\) forms a simplex in the Delaunay complex if and only if their corresponding Voronoi cells have a non-empty intersection: \[\bigcap_{u \in \sigma} V_u \ne \emptyset\]
- Edges: Two sites are connected if their Voronoi cells share an edge.
- Triangles: Three sites form a triangle if their cells meet at a single vertex.
Delaunay Complexes
The Čech Complex
- A simplex is included if the balls of radius r centered at its points have a common intersection.
- Formally, it is the nerve of the collection of balls \(B_x(r)\) for all points \(x\) in the dataset.
- Challenge: Computationally expensive, as it requires checking for the intersection of many combinations of balls.
\[ \text{Čech}(r) = \{ \sigma \subseteq S \mid \bigcap_{x \in \sigma} B_x(r) \neq \emptyset \} \]
The Vietoris-Rips (VR) Complex
- A simplex \(\sigma\) is included if every pair of points in \(\sigma\) is no more than a distance of \(2r\) apart.
- Advantage: Much faster to compute than the Čech complex, as it only requires checking pairwise distances.
\[ \text{VR}(r) = \{ \sigma \subseteq S \mid \text{diam}(\sigma) \le 2r \} \]
The Alpha Complex
- A subcomplex of the Delaunay triangulation that filters simplices based on a radius parameter \(r\).
- It provides a more geometrically accurate structure than the VR or Čech complexes.
- A simplex \(\sigma\) is included if the intersection of balls of radius \(r\) with their corresponding Voronoi cells is non-empty.
- These regions are defined as \(R_u(r) = B_u(r) \cap V_u\) for each vertex \(u\).
- As \(r\) increases, more simplices are included, until the Alpha complex becomes the full Delaunay complex.
Comparing the Complexes
- Inclusion Hierarchy: For a given radius \(r\), the complexes are nested within each other. The Alpha complex is the smallest and the Vietoris-Rips is the largest.
\[ \text{Alpha}(r) \subseteq \text{Čech}(r) \subseteq \text{Vietoris-Rips}(r) \]
Comparison
Euler Characteristic
Euler Characteristic
- Defined for a simplicial complex K as the alternating sum of the number of simplices in each dimension.
- \(\chi(K) = \sum_{p \ge 0} (-1)^p n_p\), where \(n_p\) is the number of \(p\)-simplices (e.g., vertices, edges, triangles).
- Euler-Poincaré Theorem: The Euler characteristic is also the alternating sum of its Betti numbers.
- \(\chi(K) = \sum_{p \ge 0} (-1)^p \beta_p\).
- \(\beta_p\) is the rank of the \(p\)-th homology group, representing the number of \(p\)-dimensional “holes”.
- The Euler characteristic does not depend on the specific triangulation chosen for a topological space, but is an invariant of the space itself.
Homology (Chapter IV)
A mathematical formalism for quantitatively describing the connectivity of a space, particularly its “holes”.
Homology Groups
- Chain Complex: A sequence of chain groups \(C_p\) and boundary homomorphisms \(\partial_p : C_p \to C_{p-1}\) such that the composition of any two consecutive boundary maps is zero (\(\partial_{p-1} \partial_p = 0\)).
- Chains (\(C_p\)): Formal sums of p-simplices, \(c = \sum a_i \sigma_i\). Coefficients \(a_i\) are often from \(\mathbb{Z}_2\) (modulo 2), meaning \(a_i \in \{0, 1\}\). With \(\mathbb{Z}_2\) coefficients, a chain can be viewed as a set of \(p\)-simplices. The \(p\)-chains form a group \((C_p, +)\).
- Boundary Map (\(\partial_p\)): A homomorphism \(\partial_p : C_p(K) \to C_{p-1}(K)\) that maps a \(p\)-simplex \(\sigma = [u_0, \dots, u_p]\) to the sum of its \((p-1)\)-faces: \(\partial_p \sigma = \sum_{j=0}^p [u_0, \dots, \widehat{u}_j, \dots, u_p]\).
- Cycles (\(Z_p\)) and Boundaries (\(B_p\)):
- A \(p\)-cycle is a \(p\)-chain \(c\) with an empty boundary (\(\partial_p c = 0\)). The group of \(p\)-cycles \(Z_p = \ker \partial_p\) is a subgroup of \(C_p\).
- A \(p\)-boundary is a \(p\)-chain \(c\) that is the boundary of some \((p+1)\)-chain \(d\) (\(c = \partial_{p+1} d\)). The group of \(p\)-boundaries \(B_p = \text{im } \partial_{p+1}\) is a subgroup of \(C_p\).
- The Fundamental Lemma of Homology states \(\partial_p \partial_{p+1} d = 0\), which implies that every boundary is a cycle, so \(B_p \subseteq Z_p\).
- Homology Group (\(H_p\)): The \(p\)-th homology group is the quotient group \(H_p(K) = Z_p(K) / B_p(K)\). Its elements are homology classes.
- Betti Number (\(\beta_p\)): The rank of the \(p\)-th homology group, \(\beta_p = \text{rank } H_p(K)\). For \(\mathbb{Z}_2\) coefficients, \(\beta_p = \text{rank } Z_p - \text{rank } B_p\). \(\beta_p\) counts the number of \(p\)-dimensional holes.
Exact Sequences
- A sequence of vector spaces (or groups) and homomorphisms \(\dots \xrightarrow{f_{i-1}} V_i \xrightarrow{f_i} V_{i+1} \xrightarrow{f_{i+1}} \dots\) is exact at \(V_{i+1}\) if \(\text{im } f_i = \ker f_{i+1}\).
- Long exact sequences are powerful tools for relating different homology groups.
- Mayer-Vietoris Sequence: A specific long exact sequence that relates the homology groups of a space \(K = K' \cup K''\) to the homology groups of \(K'\), \(K''\), and their intersection \(A = K' \cap K''\).
- \(\dots \to H_p(A) \to H_p(K') \oplus H_p(K'') \to H_p(K) \to H_{p-1}(A) \to \dots\).
- Provides a divide-and-conquer approach to computing homology.
Morse Functions (Chapter VI)
Real-valued functions used to analyze the topology of manifolds.
Generic Smooth Functions
- Smooth functions are preferred over general continuous functions for analysis.
- Critical Point: A point \(x \in M\) where the derivative (gradient) \(Df_x\) of \(f: M \to \mathbb{R}\) is the zero map. In local coordinates, all partial derivatives vanish.
- Non-degenerate Critical Point: A critical point \(x\) where the Hessian matrix \(H(x)\) (matrix of second partial derivatives) is non-singular (det \(H(x) \ne 0\)).
- The index of a non-degenerate critical point is the number of minus signs in the quadratic polynomial representation given by the Morse Lemma (or number of negative eigenvalues of its Hessian).
- Morse Function: A smooth function \(f: M \to \mathbb{R}\) such that (i) all its critical points are non-degenerate, and (ii) all critical points have distinct function values.
Handle Decomposition & Morse Complex
- Attaching Handles: When increasing the threshold of a Morse function \(f\), the homotopy type of the sublevel set \(M_a = f^{-1}(-\infty, a]\) changes only when \(a\) passes a critical value. This change is homotopically equivalent to attaching a \(q\)-handle, where \(q\) is the index of the critical point.
- Morse-Smale Function: A Morse function whose stable and unstable manifolds intersect transversally.
- Morse-Smale Complex: For a Morse-Smale function, its vertices are the critical points of \(f\). Cells are components of intersections of stable and unstable manifolds. Edges, for instance, are isolated integral lines connecting critical points whose indices differ by one. This complex can be used to compute Floer homology.
Piecewise Linear (PL) Functions
- Analogous concepts for functions on triangulated manifolds where the function is linear on each simplex.
- Lower Star / Lower Link:
- Lower Star (St⁻\(u_i\)): For a vertex \(u_i\) in a PL function \(f\) (where vertices are ordered by function value), St⁻\(u_i\) consists of all simplices \(\sigma\) in St \(u_i\) for which \(u_i\) is the vertex with the maximum function value.
- Lower Link (Lk⁻\(u_i\)): Simplices in Lk \(u_i\) whose vertices all have function values less than \(f(u_i)\).
- PL Critical Vertex: A vertex \(u_i\) is a simple PL critical vertex of index \(q\) if its lower link Lk⁻\(u_i\) has the reduced homology of a \((q-1)\)-sphere (i.e., \(\widetilde{\beta}_{q-1}(\text{Lk}^-u_i)=1\) and other reduced Betti numbers are 0).
- PL Morse Function: A PL function where each vertex is either PL regular (lower link homologically trivial) or simple PL critical, and all vertices have distinct function values.
Reeb Graphs
- Visualizes the evolution of the connected components of level sets of a function \(f: X \to \mathbb{R}\).
- The Reeb graph \(R(f)\) is the quotient space where points in \(X\) are equivalent if they belong to the same connected component of the same level set.
- Nodes in the Reeb graph typically correspond to critical points of \(f\) where the topology of the level set components changes (merge or split).
- If \(X\) is contractible (e.g., a cube in medical imaging), \(R(f)\) is a tree (called a contour tree).
- Can be constructed by sweeping through function values and tracking changes in level set components.
Persistence (Chapter VII)
Measures the scale or resolution of topological features within data, particularly useful for handling noise.
Persistent Homology
- Filtration: A nested sequence of simplicial complexes \(\emptyset = K_0 \subseteq K_1 \subseteq \dots \subseteq K_n = K\). This sequence is often derived from a monotonic function \(f: K \to \mathbb{R}\) where \(K_i = K(a_i) = f^{-1}(-\infty, a_i]\) for sorted values \(a_i\).
- Birth and Death: As one moves through the filtration:
- A homology class \(\gamma \in H_p(K_i)\) is born at \(K_i\) if it is not in the image of the map from \(H_p(K_{i-1})\) (i.e., \(\gamma \notin H_p^{i-1,i}\)).
- It dies entering \(K_j\) if it merges with an older class (born at \(K_{k}\) with \(k < i\)) when going from \(K_{j-1}\) to \(K_j\).
- The Elder Rule governs this: at a merge, the “older” class (born earlier) persists, and the “younger” one dies.
- Persistence: For a class born at \(K_i\) (value \(a_i\)) and dying at \(K_j\) (value \(a_j\)), its persistence is \(a_j - a_i\).
- Persistent Betti Number (\(\beta_{i,j}^p\)): The rank of \(H_p^{i,j} = \text{im}(f_p^{i,j}: H_p(K_i) \to H_p(K_j))\). It counts \(p\)-dimensional classes born at or before \(K_i\) that are still alive at \(K_j\).
- Persistence Diagram (Dgm\(_p(f)\)): A multiset of points \((a_i, a_j)\) in \(\overline{\mathbb{R}}^2\), where \(a_i\) is the birth value and \(a_j\) is the death value of a \(p\)-dimensional homology class. Points are above the diagonal \(y=x\); diagonal points (often added with infinite multiplicity) represent features with zero persistence. The vertical distance to the diagonal is the persistence.
Implementation
- Persistent homology can be computed efficiently using matrix reduction on a single boundary matrix \(\partial\) whose rows and columns are ordered compatibly with the filtration.
- The algorithm performs left-to-right column additions to obtain a reduced matrix \(R = \partial V\).
- The lowest one in a column \(j\) of \(R\), say at row \(i\) (i.e., \(i=\text{low}(j)\)), indicates that simplex \(\sigma_i\) (birth) is paired with simplex \(\sigma_j\) (death).
- If column \(j\) is zero, \(\sigma_j\) gives birth to a class that might persist indefinitely (or until paired later in an extended context).
- This algorithm computes all pairs \((birth, death)\) for the persistence diagram.
- Sparse matrix implementations are more efficient for large datasets, improving upon the general cubic worst-case complexity. For the 0th persistence diagram, it can be computed in nearly linear time using a union-find data structure.
Spectral Sequences
- A theoretical tool in algebraic topology that provides a way to compute homology groups of a filtered space in stages.
- The algorithm involves reducing the boundary matrix in phases, sweeping diagonally.
- The groups \(E^r_{p,q}\) in the spectral sequence represent homology classes that persist for at least \(r\) “steps” in the filtration (related to the index difference in the function values).
- The Spectral Sequence Theorem states that the total rank of \(E^r_{p,q}\) (for fixed dimension \(p+q\)) equals the number of points in the \((p+q)\)-th persistence diagram with persistence \(\ge r\).
Stability (Chapter VIII)
Concerns how persistence diagrams (and thus the measured features) change when the input function or data undergoes small perturbations.
Stability Theorems
- Bottleneck Distance (\(W_\infty(X, Y)\)): A metric between two persistence diagrams \(X\) and \(Y\). It’s the infimum, over all bijections \(\eta: X \to Y\) (matching points in \(X\) to points in \(Y\), including points on the diagonal), of the supremum \(L_\infty\)-distance between matched points: \(W_\infty(X, Y) = \inf_{\eta} \sup_{x \in X} \|x - \eta(x)\|_\infty\).
- Stability Theorem for Filtrations (and Tame Functions): A fundamental result stating that the bottleneck distance between the \(p\)-th persistence diagrams of two monotonic functions \(f, g\) on a simplicial complex \(K\) (or two tame functions on a triangulable space \(X\)) is bounded by the \(L_\infty\)-distance between the functions:
- \(W_\infty(\text{Dgm}_p(f), \text{Dgm}_p(g)) \le \|f - g\|_\infty\).
- This means small changes in the function lead to small changes in the persistence diagram (when distance is measured by \(W_\infty\)).
- Vines and Vineyards: When considering a straight-line homotopy \(f_t = (1-t)f + tg\) between two functions, the points in the persistence diagrams Dgm\(_p(f_t)\) trace out polygonal paths called “vines”. The collection of these paths is a “vineyard”. The existence of these connected vines is a manifestation of stability.
Packages
tdaverse
- ripserr
- inphr
- tdarec
- phutil
- tdarec-grant
tdaverse
- ggtda
- tdaverse
- tdaunif
- interplex
Other R Packages
- BayesTDA
- simplextree
- TDAstats
Thomas Reinke